/*
一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}，{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。3->1->2->4->5->3 方向叫作 next 方向(逆时针)，3->5->4->2->1->3 方向叫作 last 方向(顺时针)。
山峰 A 和 山峰 B 能够相互看见的条件为:
1. 如果 A 和 B 是同一座山，认为不能相互看见。
2. 如果 A 和 B 是不同的山，并且在环中相邻，认为可以相互看见。
3. 如果 A 和 B 是不同的山，并且在环中不相邻，假设两座山高度的最小值为 min。如果 A 通过 next 方向到 B 的途中没有高度比 min 大的山峰，或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰，认为 A 和 B 可以相互看见。
问题如下：
给定一个不含有负数可能有重复值的数组 arr，请问有多少对山峰能够相互看见？
例如: 3 1 2 4 5  答案7

思路:
首先找到第一个最高的山峰maxIndex,单调栈(栈顶小->大)记录{高度,出现次数},找下一个山峰index
不能入栈则弹出，然后开始计算，假设弹出的山峰有k个，则他们两两可以相互看见,Ck2个(排列组合), 同时因为要弹出
index的山峰肯定比栈pop的山要高，同时peek山没有maxIndex高，所以每个pop的山都有两个可以看见的山, 2*k
如果peek山>index， 入栈，如果peek山===index，peek.出现次数++

开始清算栈,
只要不是倒数的2个元素，一律按照Ck2 + 2*k计算
倒数第二个，如果最后一个(maxIndex)山有>1个， 那么就是Ck2+2*k，如果maxIndex只有一座，Ck2+k
最后一个， Ck2cc
 */

Array.prototype.peek = function () {
  return this[this.length - 1]
}

/**
 * @param {number} size
 * @param {number}curIndex
 * @return {number}
 */
function nextIndex (size, curIndex) {
  return (curIndex + 1) % size
}

/**
 * 计算Ck2
 * @param {number} counts
 * @return {number}
 */
function getInternalSum (counts) {
  return counts < 2 ? 0 : counts * (counts - 1) / 2
}

// 计数类，放入stack中
class Item {
  constructor (value, count) {
    this.value = value
    this.count = count
  }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
function pairOfMountains (arr) {
  let pairs = 0 // 山峰对的数量
  let maxIndex = 0 // 最大值的index
  const n = arr.length
  for (let i = 0; i < n; i++) {
    maxIndex = arr[i] > arr[maxIndex] ? i : maxIndex
  }
  const monoStack = []
  monoStack.push(new Item(arr[maxIndex], 1))
  let index = nextIndex(n, maxIndex) // 下一个位置
  while (index !== maxIndex) {
    while (monoStack.length && monoStack.peek().value < arr[index]) {
      const item = monoStack.pop()
      pairs += getInternalSum(item.count) + 2 * item.count
    }
    if (monoStack.length && arr[monoStack.peek()] === arr[index]) {
      monoStack.peek().count++
    } else {
      monoStack.push(new Item(arr[index], 1))
    }
    index = nextIndex(n, index)
  }
  // 清算过程
  while (monoStack.length) {
    const item = monoStack.pop()
    pairs += getInternalSum(item.count)
    if (monoStack.length) {
      pairs += item.count
      if (monoStack.length > 1) {
        pairs += item.count
      } else {
        pairs += monoStack.peek().count > 1 ? item.count : 0
      }
    }
  }
  return pairs
}

console.log(pairOfMountains([3, 1, 2, 4, 5]))
